package fun.ticsmyc.question;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * peek()//返回队首元素
 * poll()//返回队首元素，队首元素出队列
 * add()//添加元素
 * size()//返回队列元素个数
 * isEmpty()//判断队列是否为空，为空返回true,不空返回false
 *
 * @author Ticsmyc
 * @package fun.ticsmyc.question
 * @date 2020-02-11 15:52
 */
public class 双堆_优先队列_求中位数 {

////////////////////使用优先队列。。待填坑
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1,o2)->{return o2-o1;});
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>(new MinHeapComparator());


    private void modifyTwoHeapsSize(){
        if(maxHeap.size() - minHeap.size()>1){
            //大顶堆多了
            minHeap.add(maxHeap.poll());
        }
        if(minHeap.size() -maxHeap.size() >1){
            //小顶堆多了
            maxHeap.add(minHeap.poll());
        }
    }

    public void addNumber(int num){
        if(maxHeap.isEmpty()){
            //大顶堆为空
            maxHeap.add(num);
            return;
        }
        if(maxHeap.peek() >= num){
            maxHeap.add(num);
        }else{
            if(minHeap.isEmpty()){
                //小顶堆空
                minHeap.add(num);
                return;
            }
            if(minHeap.peek() <num){
                minHeap.add(num);
            }else{
                maxHeap.add(num);
            }
        }
        modifyTwoHeapsSize();
    }

    public double getMedian(){
        int maxHeapSize = maxHeap.size();
        int minHeapSize = minHeap.size();

        if((maxHeapSize+minHeapSize)%2 ==0 ){
            return (double)(maxHeap.peek()+minHeap.peek())/2;
        }else{
            return maxHeapSize>minHeapSize ? maxHeap.peek():minHeap.peek();
        }

    }

    public static class MaxHeapComparator implements Comparator<Integer> {
        /**
         * 从大到小排序
         * @param o1
         * @param o2
         * @return
         */
        @Override
        public int compare(Integer o1, Integer o2) {
            if (o2 > o1) {
                return 1;
            } else {
                return -1;
            }
        }
    }

    public static class MinHeapComparator implements Comparator<Integer> {
        /**
         * 从小到大排序
         * @param o1
         * @param o2
         * @return
         */
        @Override
        public int compare(Integer o1, Integer o2) {
            if (o2 < o1) {
                return 1;
            } else {
                return -1;
            }
        }
    }



    // for test
    public static int[] getRandomArray(int maxLen, int maxValue) {
        int[] res = new int[(int) (Math.random() * maxLen) + 1];
        for (int i = 0; i != res.length; i++) {
            res[i] = (int) (Math.random() * maxValue);
        }
        return res;
    }

    // for test, this method is ineffective but absolutely right
    public static double getMedianOfArray(int[] arr) {
        int[] newArr = Arrays.copyOf(arr, arr.length);
        Arrays.sort(newArr);
        int mid = (newArr.length - 1) / 2;
        if ((newArr.length & 1) == 0) {
            return (double)(newArr[mid] + newArr[mid + 1]) / 2;
        } else {
            return newArr[mid];
        }
    }

    public static void printArray(int[] arr) {
        for (int i = 0; i != arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        boolean err = false;
        int testTimes = 200000;
        for (int i = 0; i != testTimes; i++) {
            int len = 30;
            int maxValue = 1000;
            int[] arr = getRandomArray(len, maxValue);
            双堆_优先队列_求中位数 medianHold = new 双堆_优先队列_求中位数();
            for (int j = 0; j != arr.length; j++) {
                medianHold.addNumber(arr[j]);
            }
            if (medianHold.getMedian() != getMedianOfArray(arr)) {
                err = true;
                printArray(arr);
                break;
            }
        }
        System.out.println(err ? "Oops..what a fuck!" : "today is a beautiful day^_^");

    }

}
